PC World 2000 February

home *** CD-ROM | disk | FTP | other *** search

/ PC World 2000 February / PCWorld_2000-02_cd.bin / Software / Servis / FFE / MISC.SWG / 0001_TIFF-BMP-LZW ALGORITHMS.pas next >

Wrap

Pascal/Delphi Source File | 1996-09-04 | 33.5 KB | 679 lines

--------!-ALGORITHMS------------------------ Some algorithms used for encoding images etc... --- TIFF PackBits algorithm Abstract This document describes a simple compression scheme for bilevel scanned and paint type files. Motivation The TIFF specification defines a number of compression schemes. Compression type 1 is really no compression, other than basic pixel packing. Compression type 2, based on CCITT 1D compression, is powerful, but not trivial to implement. Compression type 5 is typically very effective for most bilevel images, as well as many deeper images such as palette color and grayscale images, but is also not trivial to implement. PackBits is a simple but often effective alternative. Description Several good schemes were already in use in various settings. We somewhat arbitrarily picked the Macintosh PackBits scheme. It is byte oriented, so there is no problem with word alignment. And it has a good worst case behavior (at most 1 extra byte for every 128 input bytes). For Macintosh users, there are toolbox utilities PackBits and UnPackBits that will do the work for you, but it is easy to implement your own routines. A pseudo code fragment to unpack might look like this: Loop until you get the number of unpacked bytes you are expecting: Read the next source byte into n. If n is between 0 and 127 inclusive, copy the next n+1 bytes literally. Else if n is between -127 and -1 inclusive, copy the next byte -n+1 times. Else if n is 128, noop. Endloop In the inverse routine, it's best to encode a 2-byte repeat run as a replicate run except when preceded and followed by a literal run, in which case it's best to merge the three into one literal run. Always encode 3-byte repeats as replicate runs. So that's the algorithm. Here are some other rules: o Each row must be packed separately. Do not compress across row boundaries. o The number of uncompressed bytes per row is defined to be (ImageWidth + 7) / 8. If the uncompressed bitmap is required to have an even number of bytes per row, decompress into word- aligned buffers. o If a run is larger than 128 bytes, simply encode the remainder of the run as one or more additional replicate runs. When PackBits data is uncompressed, the result should be interpreted as per compression type 1 (no compression). --- TIFF LZW Compression Abstract This document describes an adaptive compression scheme for raster images. Reference Terry A. Welch, "A Technique for High Performance Data Compression", IEEE Computer, vol. 17 no. 6 (June 1984). Describes the basic Lempel-Ziv & Welch (LZW) algorithm. The author's goal in the article is to describe a hardware-based compressor that could be built into a disk controller or database engine, and used on all types of data. There is no specific discussion of raster images. We intend to give sufficient information in this Appendix so that the article is not required reading. Requirements A compression scheme with the following characteristics should work well in a desktop publishing environment: o Must work well for images of any bit depth, including images deeper than 8 bits per sample. o Must be effective: an average compression ratio of at least 2:1 or better. And it must have a reasonable worst-case behavior, in case something really strange is thrown at it. o Should not depend on small variations between pixels. Palette color images tend to contain abrupt changes in index values, due to common patterning and dithering techniques. These abrupt changes do tend to be repetitive, however, and the scheme should make use of this fact. o For images generated by paint programs, the scheme should not depend on a particular pattern width. 8x8 pixel patterns are common now, but we should not assume that this situation will not change. o Must be fast. It should not take more than 5 seconds to decompress a 100K byte grayscale image on a 68020- or 386-based computer. Compression can be slower, but probably not by more than a factor of 2 or 3. o The level of implementation complexity must be reasonable. We would like something that can be implemented in no more than a couple of weeks by a competent software engineer with some experience in image processing. The compiled code for compression and decompression combined should be no more than about 10K. o Does not require floating point software or hardware. The following sections describe an algorithm based on the "LZW" (Lempel-Ziv & Welch) technique that meets the above requirements. In addition meeting our requirements, LZW has the following characteristics: o LZW is fully reversible. All information is preserved. But if noise or information is removed from an image, perhaps by smoothing or zeroing some low-order bitplanes, LZW compresses images to a smaller size. Thus, 5-bit, 6-bit, or 7-bit data masquerading as 8-bit data compresses better than true 8-bit data. Smooth images also compress better than noisy images, and simple images compress better than complex images. o On a 68082- or 386-based computer, LZW software can be written to compress at between 30K and 80K bytes per second, depending on image characteristics. LZW decompression speeds are typically about 50K bytes per second. o LZW works well on bilevel images, too. It always beats PackBits, and generally ties CCITT 1D (Modified Huffman) compression, on our test images. Tying CCITT 1D is impressive in that LZW seems to be considerably faster than CCITT 1D, at least in our implementation. o Our implementation is written in C, and compiles to about 2K bytes of object code each for the compressor and decompressor. o One of the nice things about LZW is that it is used quite widely in other applications such as archival programs, and is therefore more of a known quantity. The Algorithm Each strip is compressed independently. We strongly recommend that RowsPerStrip be chosen such that each strip contains about 8K bytes before compression. We want to keep the strips small enough so that the compressed and uncompressed versions of the strip can be kept entirely in memory even on small machines, but large enough to maintain nearly optimal compression ratios. The LZW algorithm is based on a translation table, or string table, that maps strings of input characters into codes. The TIFF implementation uses variable-length codes, with a maximum code length of 12 bits. This string table is different for every strip, and, remarkably, does not need to be kept around for the decompressor. The trick is to make the decompressor automatically build the same table as is built when compressing the data. We use a C-like pseudocode to describe the coding scheme: InitializeStringTable(); WriteCode(ClearCode); Omega = the empty string; for each character in the strip { K = GetNextCharacter(); if Omega+K is in the string table { Omega = Omega+K; /* string concatenation */ } else { WriteCode (CodeFromString(Omega)); AddTableEntry(Omega+K); Omega = K; } } /* end of for loop */ WriteCode (CodeFromString(Omega)); WriteCode (EndOfInformation); That's it. The scheme is simple, although it is fairly challenging to implement efficiently. But we need a few explanations before we go on to decompression. The "characters" that make up the LZW strings are bytes containing TIFF uncompressed (Compression=1) image data, in our implementation. For example, if BitsPerSample is 4, each 8-bit LZW character will contain two 4-bit pixels. If BitsPerSample is 16, each 16-bit pixel will span two 8-bit LZW characters. (It is also possible to implement a version of LZW where the LZW character depth equals BitsPerSample, as was described by Draft 2 of Revision 5.0. But there is a major problem with this approach. If BitsPerSample is greater than 11, we can not use 12-bit-maximum codes, so that the resulting LZW table is unacceptably large. Fortunately, due to the adaptive nature of LZW, we do not pay a significant compression ratio penalty for combining several pixels into one byte before compressing. For example, our 4-bit sample images compressed about 3 percent worse, and our 1-bit images compressed about 5 percent better. And it is easier to write an LZW compressor that always uses the same character depth than it is to write one which can handle varying depths.) We can now describe some of the routine and variable references in our pseudocode: InitializeStringTable() initializes the string table to contain all possible single-character strings. There are 256 of them, numbered 0 through 255, since our characters are bytes. WriteCode() writes a code to the output stream. The first code written is a Clear code, which is defined to be code #256. Omega is our "prefix string." GetNextCharacter() retrieves the next character value from the input stream. This will be number between 0 and 255, since our characters are bytes. The "+" signs indicate string concatenation. AddTableEntry() adds a table entry. (InitializeStringTable() has already put 256 entries in our table. Each entry consists of a single-character string, and its associated code value, which is, in our application, identical to the character itself. That is, the 0th entry in our table consists of the string <0>, with corresponding code value of <0>, the 1st entry in the table consists of the string <1>, with corresponding code value of <1>, ..., and the 255th entry in our table consists of the string <255>, with corresponding code value of <255>.) So the first entry that we add to our string table will be at position 256, right? Well, not quite, since we will reserve code #256 for a special "Clear" code, and code #257 for a special "EndOfInformation" code that we will write out at the end of the strip. So the first multiple-character entry added to the string table will be at position 258. Let's try an example. Suppose we have input data that looks like: Pixel 0: <7> Pixel 1: <7> Pixel 2: <7> Pixel 3: <8> Pixel 4: <8> Pixel 5: <7> Pixel 6: <7> Pixel 7: <6> Pixel 8: <6> First, we read Pixel 0 into K. OmegaK is then simply <7>, since Omega is the empty string at this point. Is the string <7> already in the string table? Of course, since all single character strings were put in the table by InitializeStringTable(). So set Omega equal to <7>, and go to the top of the loop. Read Pixel 1 into K. Does OmegaK (<7><7>) exist in the string table? No, so we get to do some real work. We write the code associated with Omega to output (write <7> to output), and add OmegaK (<7><7>) to the table as entry 258. Store K (<7>) into Omega. Note that although we have added the string consisting of Pixel 0 and Pixel 1 to the table, we "re-use" Pixel 1 as the beginning of the next string. Back at the top of the loop. We read Pixel 2 into K. Does OmegaK (<7><7>) exist in the string table? Yes, the entry we just added, entry 258, contains exactly <7><7>. So we just add K onto the end of Omega, so that Omega is now <7><7>. Back at the top of the loop. We read Pixel 3 into K. Does OmegaK (<7><7><8>) exist in the string table? No, so write the code associated with Omega (<258>) to output, and add OmegaK to the table as entry 259. Store K (<8>) into Omega. Back at the top of the loop. We read Pixel 4 into K. Does OmegaK (<8><8>) exist in the string table? No, so write the code associated with Omega (<8>) to output, and add OmegaK to the table as entry 260. Store K (<8>) into Omega. Continuing, we get the following results: After reading: We write to output: And add table entry: Pixel 0 Pixel 1 <7> 258: <7><7> Pixel 2 Pixel 3 <258> 259: <7><7><8> Pixel 4 <8> 260: <8><8> Pixel 5 <8> 261: <8><7> Pixel 6 Pixel 7 <258> 262: <7><7><6> Pixel 8 <6> 263: <6><6> WriteCode() also requires some explanation. The output code stream, <7><258><8><8><258><6>... in our example, should be written using as few bits as possible. When we are just starting out, we can use 9-bit codes, since our new string table entries are greater than 255 but less than 512. But when we add table entry 512, we must switch to 10-bit codes. Likewise, we switch to 11-bit codes at 1024, and 12-bit codes at 2048. We will somewhat arbitrarily limit ourselves to 12-bit codes, so that our table can have at most 4096 entries. If we push it any farther, tables tend to get too large. What happens if we run out of room in our string table? This is where the afore-mentioned Clear code comes in. As soon as we use entry 4094, we write out a (12-bit) Clear code. (If we wait any dworder to write the Clear code, the decompressor might try to interpret the Clear code as a 13-bit code.) At this point, the compressor re-initializes the string table and starts writing out 9-bit codes again. Note that whenever you write a code and add a table entry, Omega is not left empty. It contains exactly one character. Be careful not to lose it when you write an end-of-table Clear code. You can either write it out as a 12-bit code before writing the Clear code, in which case you will want to do it right after adding table entry 4093, or after the clear code as a 9-bit code. Decompression gives the same result in either case. To make things a little simpler for the decompressor, we will require that each strip begins with a Clear code, and ends with an EndOfInformation code. Every LZW-compressed strip must begin on a byte boundary. It need not begin on a word boundary. LZW compression codes are stored into bytes in high-to-low-order fashion, i.e., FillOrder is assumed to be 1. The compressed codes are written as bytes, not words, so that the compressed data will be identical regardless of whether it is an "II" or "MM" file. Note that the LZW string table is a continuously updated history of the strings that have been encountered in the data. It thus reflects the characteristics of the data, providing a high degree of adaptability. LZW Decoding The procedure for decompression is a little more complicated, but still not too bad: while ((Code = GetNextCode()) != EoiCode) { if (Code == ClearCode) { InitializeTable(); Code = GetNextCode(); if (Code == EoiCode) break; WriteString(StringFromCode(Code)); OldCode = Code; } /* end of ClearCode case */ else { if (IsInTable(Code)) { WriteString(StringFromCode(Code)); AddStringToTable(StringFromCode(OldCode)+ FirstChar(StringFromCode(Code))); OldCode = Code; } else { OutString = StringFromCode(OldCode) + FirstChar(StringFromCode(OldCode)); WriteString(OutString); AddStringToTable(OutString); OldCode = Code; } } /* end of not-ClearCode case */ } /* end of while loop */ The function GetNextCode() retrieves the next code from the LZW- coded data. It must keep track of bit boundaries. It knows that the first code that it gets will be a 9-bit code. We add a table entry each time we get a code, so GetNextCode() must switch over to 10-bit codes as soon as string #511 is stored into the table. The function StringFromCode() gets the string associated with a particular code from the string table. The function AddStringToTable() adds a string to the string table. The "+" sign joining the two parts of the argument to AddStringToTable indicate string concatenation. StringFromCode() looks up the string associated with a given code. WriteString() adds a string to the output stream. When SamplesPerPixel Is Greater Than 1 We have so far described the compression scheme as if SamplesPerPixel were always 1, as will be be the case with palette color and grayscale images. But what do we do with RGB image data? Tests on our sample images indicate that the LZW compression ratio is nearly identical regardless of whether PlanarConfiguration=1 or PlanarConfiguration=2, for RGB images. So use whichever configuration you prefer, and simply compress the bytes in the strip. It is worth cautioning that compression ratios on our test RGB images were disappointing low: somewhere between 1.1 to 1 and 1.5 to 1, depending on the image. Vendors are urged to do what they can to remove as much noise from their images as possible. Preliminary tests indicate that significantly better compression ratios are possible with less noisy images. Even something as simple as zeroing out one or two least-significant bitplanes may be quite effective, with little or no perceptible image degradation. Implementation The exact structure of the string table and the method used to determine if a string is already in the table are probably the most significant design decisions in the implementation of a LZW compressor and decompressor. Hashing has been suggested as a useful technique for the compressor. We have chosen a tree based approach, with good results. The decompressor is actually more straightforward, as well as faster, since no search is involved - strings can be accessed directly by code value. Performance Many people do not realize that the performance of any compression scheme depends greatly on the type of data to which it is applied. A scheme that works well on one data set may do poorly on the next. But since we do not want to burden the world with too many compression schemes, an adaptive scheme such as LZW that performs quite well on a wide range of images is very desirable. LZW may not always give optimal compression ratios, but its adaptive nature and relative simplicity seem to make it a good choice. Experiments thus far indicate that we can expect compression ratios of between 1.5 and 3.0 to 1 from LZW, with no loss of data, on continuous tone grayscale scanned images. If we zero the least significant one or two bitplanes of 8-bit data, higher ratios can be achieved. These bitplanes often consist chiefly of noise, in which case little or no loss in image quality will be perceived. Palette color images created in a paint program generally compress much better than continuous tone scanned images, since paint images tend to be more repetitive. It is not unusual to achieve compression ratios of 10 to 1 or better when using LZW on palette color paint images. By way of comparison, PackBits, used in TIFF for black and white bilevel images, does not do well on color paint images, much less continuous tone grayscale and color images. 1.2 to 1 seemed to be about average for 4-bit images, and 8-bit images are worse. It has been suggested that the CCITT 1D scheme could be used for continuous tone images, by compressing each bitplane separately. No doubt some compression could be achieved, but it seems unlikely that a scheme based on a fixed table that is optimized for word black runs separated by dworder white runs would be a very good choice on any of the bitplanes. It would do quite well on the high-order bitplanes (but so would a simpler scheme like PackBits), and would do quite poorly on the low-order bitplanes. We believe that the compression ratios would generally not be very impressive, and the process would in addition be quite slow. Splitting the pixels into bitplanes and putting them back together is somewhat expensive, and the coding is also fairly slow when implemented in software. Another approach that has been suggested uses uses a 2D differencing step following by coding the differences using a fixed table of variable-length codes. This type of scheme works quite well on many 8-bit grayscale images, and is probably simpler to implement than LZW. But it has a number of disadvantages when used on a wide variety of images. First, it is not adaptive. This makes a big difference when compressing data such as 8-bit images that have been "sharpened" using one of the standard techniques. Such images tend to get larger instead of smaller when compressed. Another disadvantage of these schemes is that they do not do well with a wide range of bit depths. The built-in code table has to be optimized for a particular bit depth in order to be effective. Finally, we should mention "lossy" compression schemes. Extensive research has been done in the area of lossy, or non- information-preserving image compression. These techniques generally yield much higher compression ratios than can be achieved by fully-reversible, information-preserving image compression techniques such as PackBits and LZW. Some disadvantages: many of the lossy techniques are so computationally expensive that hardware assists are required. Others are so complicated that most microcomputer software vendors could not afford either the expense of implementation or the increase in application object code size. Yet others sacrifice enough image quality to make them unsuitable for publishing use. In spite of these difficulties, we believe that there will one day be a standardized lossy compression scheme for full color images that will be usable for publishing applications on microcomputers. An International Standards Organization group, ISO/IEC/JTC1/SC2/WG8, in cooperation with CCITT Study Group VIII, is hard at work on a scheme that might be appropriate. We expect that a future revision of TIFF will incorporate this scheme once it is finalized, if it turns out to satisfy the needs of desktop publishers and others in the microcomputer community. This will augment, not replace, LZW as an approved TIFF compression scheme. LZW will very likely remain the scheme of choice for Palette color images, and perhaps 4-bit grayscale images, and may well overtake CCITT 1D and PackBits for bilevel images. Future LZW Extensions Some images compress better using LZW coding if they are first subjected to a process wherein each pixel value is replaced by the difference between the pixel and the preceding pixel. Performing this differencing in two dimensions helps some images even more. However, many images do not compress better with this extra preprocessing, and for a significant number of images, the compression ratio is actually worse. We are therefore not making differencing an integral part of the TIFF LZW compression scheme. However, it is possible that a "prediction" stage like differencing may exist which is effective over a broad range of images. If such a scheme is found, it may be incorporated in the next major TIFF revision. If so, a new value will be defined for the new "Predictor" TIFF tag. Therefore, all TIFF readers that read LZW files must pay attention to the Predictor tag. If it is 1, which is the default case, LZW decompression may proceed safely. If it is not 1, and the reader does not recognize the specified prediction scheme, the reader should give up. Acknowledgements The original LZW reference has already been given. The use of ClearCode as a technique to handle overflow was borrowed from the compression scheme used by the Graphics Interchange Format (GIF), a small-color-paint-image-file format used by CompuServe that also is an adaptation of the LZW technique. Joff Morgan and Eric Robinson of Aldus were each instrumental in their own way in getting LZW off the ground. The TIFF predictor algorithm The idea is to make use of the fact that many continuous tone images rarely vary much in pixel value from one pixel to the next. In such images, if we replace the pixel values by differences between consecutive pixels, many of the differences should be 0, plus or minus 1, and so on. This reduces the apparent information content, and thus allows LZW to encode the data more compactly. Assuming 8-bit grayscale pixels for the moment, a basic C implementation might look something like this: char image[ ][ ]; int row, col; /* take horizontal differences: */ for (row = 0; row < nrows; row++) for (col = ncols - 1; col >= 1; col--) image[row][col] -= image[row][col-1]; If we don't have 8-bit samples, we need to work a little harder, so that we can make better use of the architecture of most CPUs. Suppose we have 4-bit samples, packed two to a byte, in normal TIFF uncompressed (i.e., Compression=1) fashion. In order to find differences, we want to first expand each 4-bit sample into an 8-bit byte, so that we have one sample per byte, low-order justified. We then perform the above horizontal differencing. Once the differencing has been completed, we then repack the 4- bit differences two to a byte, in normal TIFF uncompressed fashion. If the samples are greater than 8 bits deep, expanding the samples into 16-bit words instead of 8-bit bytes seems like the best way to perform the subtraction on most computers. Note that we have not lost any data up to this point, nor will we lose any data later on. It might at first seem that our differencing might turn 8-bit samples into 9-bit differences, 4- bit samples into 5-bit differences, and so on. But it turns out that we can completely ignore the "overflow" bits caused by subtracting a larger number from a smaller number and still reverse the process without error. Normal twos complement arithmetic does just what we want. Try an example by hand if you need more convincing. Up to this point we have implicitly assumed that we are compressing bilevel or grayscale images. An additional consideration arises in the case of color images. If PlanarConfiguration is 2, there is no problem. Differencing proceeds the same way as it would for grayscale data. If PlanarConfiguration is 1, however, things get a little trickier. If we didnt do anything special, we would be subtracting red sample values from green sample values, green sample values from blue sample values, and blue sample values from red sample values, which would not give the LZW coding stage much redundancy to work with. So we will do our horizontal differences with an offset of SamplesPerPixel (3, in the RGB case). In other words, we will subtract red from red, green from green, and blue from blue. The LZW coding stage is identical to the SamplesPerPixel=1 case. We require that BitsPerSample be the same for all 3 samples. Results and guidelines LZW without differencing works well for 1-bit images, 4-bit grayscale images, and synthetic color images. But natural 24-bit color images and some 8-bit grayscale images do much better with differencing. For example, our 24-bit natural test images hardly compressed at all using "plain" LZW: the average compression ratio was 1.04 to 1. The average compression ratio with horizontal differencing was 1.40 to 1. (A compression ratio of 1.40 to 1 means that if the uncompressed image is 1.40MB in size, the compressed version is 1MB in size.) Although the combination of LZW coding with horizontal differencing does not result in any loss of data, it may be worthwhile in some situations to give up some information by removing as much noise as possible from the image data before doing the differencing, especially with 8-bit samples. The simplest way to get rid of noise is to mask off one or two low- order bits of each 8-bit sample. On our 24-bit test images, LZW with horizontal differencing yielded an average compression ratio of 1.4 to 1. When the low-order bit was masked from each sample, the compression ratio climbed to 1.8 to 1; the compression ratio was 2.4 to 1 when masking two bits, and 3.4 to 1 when masking three bits. Of course, the more you mask, the more you risk losing useful information adword with the noise. We encourage you to experiment to find the best compromise for your device. For some applications it may be useful to let the user make the final decision. Interestingly, most of our RGB images compressed slightly better using PlanarConfiguration=1. One might think that compressing the red, green, and blue difference planes separately (PlanarConfiguration=2) might give better compression results than mixing the differences together before compressing (PlanarConfiguration=1), but this does not appear to be the case. Incidentally, we tried taking both horizontal and vertical differences, but the extra complexity of two-dimensional differencing did not appear to pay off for most of our test images. About one third of the images compressed slightly better with two-dimensional differencing, about one third compressed slightly worse, and the rest were about the same. --- BMP RLE_8 compression The BMP can be compressed in two modes, absolute mode and RLE mode. Both modes can occur anywhere in a single bitmap. The RLE mode is a simple RLE mechanism, the first byte contains the count, the second byte the pixel to be replicatet. If the count byte is 0, the second byte is a special, like EOL or delta. In absolute mode, the second byte contains the number of bytes to be copied litteraly. Each absolute run must be word-aligned that means you will may have to add an aditional padding byte which is not included in the count. After an absolute run, RLE compression continues. Second byte Meaning 0 End of line 1 End of bitmap 2 Delta. The next two bytes are the horizontal and vertical offsets from the current position to the next pixel. 3-255 Switch to absolute mode --- BMP RLE_4 compression RLE_4 compression knows the two modes of the RLE_8 compression, absolute and RLE. In the RLE mode, the first byte contains the count of pixels to draw, the second byte contains in its two nibbles the indices off the pixel colors, the higher 4 bits are the left pixel, the lower 4 bits are the right pixel. Note that two-color runs are possible to encode with RLE_4 through this. --- Protracker sample compression / decompression Get the number of sample bytes to process. Call this SamplesLeft. Set Delta counter to 0. DO Get a byte from the buffer. Store the byte in Temp. Subtract the Delta counter from the byte. Store it in the buffer. Move the Temp byte into the Delta Counter Decrement SamplesLeft. WHILE(SamplesLeft <> 0) The technique for conversion back to the raw data is: Get the number of sample bytes to process. Call this SamplesLeft. Set Delta counter to 0. DO Get a byte from the buffer. Add onto the byte the Delta Counter. Store the byte in Delta Counter. Store the byte in Temp. Decrement SamplesLeft. WHILE(SamplesLeft <> 0)